A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs

摘要

The multicast capacity of a directed network is closely related to the$s$-$t$ maximum flow, which is equal to the $s$-$t$ minimum cut capacity due tothe max-flow min-cut theorem. If the topology of a network (or link capacities)is dynamically changing or have stochastic nature, it is not so trivial topredict statistical properties on the maximum flow. In this paper, we present acoding theoretic approach for evaluating the accumulate distribution of theminimum cut capacity of weighted random graphs. The main feature of ourapproach is to utilize the correspondence between the cut space of a graph anda binary LDGM (low-density generator-matrix) code with column weight 2. Thegraph ensemble treated in the paper is a weighted version ofErd\H{o}s-R\'{e}nyi random graph ensemble. The main contribution of our work isa combinatorial lower bound for the accumulate distribution of the minimum cutcapacity. From some computer experiments, it is observed that the lower boundderived here reflects the actual statistical behavior of the minimum cutcapacity.